11173. Коды Грея

 

Бинарные коды Грея генерируются следующим образом. Рассмотри последовательность

0

1

-

Отобразим строки вниз относительно горизонтальной черты, припишем к первой половине строк спереди 0, а ко второй отображенной половине 1. Получим последовательность:

00
01
11
10

Продолжая процесс, на следующем шаге получим последовательность из 8 чисел. Справа от кода находится его десятичное значение.

000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4

Приведенные последовательности называются кодами Грея длины n = 1, 2, 3. Всего существует 2n разных кодов длины n. Каждые два соседних кода отличаются одним битом.

 

Вход. Первая строка содержит количество тестов (не более 250000). Каждая следующая строка содержит два числа: n (1 £ n £ 30) и k (0 £ k < 2n).

 

Выход. Для каждого теста вывести число, которое находится в k - ой позиции последовательности кодов Грея длины n.

 

Пример входа

Пример выхода

14

1 0

1 1

2 0

2 1

2 2

2 3

3 0

3 1

3 2

3 3

3 4

3 5

3 6

3 7

0

1

0

1

3

2

0

1

3

2

6

7

5

4

 

 

РЕШЕНИЕ

рекурсия + комбинаторика

 

Анализ алгоритма

Запишем рекурсивную функцию find(n, k), которая будет находить число в k - ой позиции последовательности кодов Грея длины n. Если значение k лежит в первой части последовательности (k < 2n-1), то следует искать число, стоящее в k - ой позиции кодов Грея длины n – 1. Иначе воспользуемся симметрией при построении кодов Грея: результат будет равен 2n-1 плюс число, стоящее в (2n –  k – 1) - ой позиции кодов Грея длины n – 1.

 

Реализация алгоритма

Функция find(n, k) находит число, которое находится в k - ой позиции последовательности кодов Грея длины n.

 

int find(int n, int k)

{

  if (!n) return 0;

  int temp = 1 << (n-1);

  if (k < temp) return find(n-1,k);

  return temp + find(n-1, (1 << n) - 1 - k);

}

 

Основной цикл программы. Читаем количество тестов tests. Для каждого теста читаем входные данные n и k. Вычисляем и выводим значение find(n, k).

 

scanf("%d",&tests);

while(tests--)

{

  scanf("%d %d",&n,&k);

  res = find(n,k);

  printf("%d\n",res);

}